Skip to Main Content

Press the up and down arrow key to navigate

Goals

Take a free course

Subjects

Browse all subjects

Earn a Degree

Breakthrough pricing on 100% online degrees designed to fit into your life.

Data Science

University of Colorado Boulder

Master of Science in Data Science

University of Illinois at Urbana-Champaign

Master in Computer Science

View all Data Science degrees

Business

University of Illinois at Urbana-Champaign

Master of Business Administration (iMBA)

University of Illinois at Urbana-Champaign

Master of Science in Management

View all Business degrees

Computer Science

Penn Engineering

Master of Computer and Information Technology

Arizona State University

Master of Computer Science

View all Computer Science degrees

More Degrees

Public Health Bachelor's Degrees Engineering Master's Degrees Social Sciences

Earn credit toward a master's

Big Data MasterTrack® Certificate

Degree credit•Expert feedback

Innovation Management & Entrepreneurship MasterTrack® Certificate

Degree credit•Expert feedback

View all MasterTrack Certificates

Earn a Certificate

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Data Science

Google Data Analytics

No prerequisites•Self-paced

IBM Data Science

No prerequisites•Self-paced

Machine Learning for Analytics MasterTrack® Certificate

Expert feedback•Credit eligible

View all Data Science Certificates

Business

Facebook Social Media Marketing

No prerequisites•Self-paced

Google Project Management:

No prerequisites•Self-paced

IBM Machine Learning

View all Business Certificates

Computer Science

AI and Machine Learning MasterTrack® Certificate

Expert feedback•Credit eligible

DeepLearning.AI TensorFlow Developer

Certification preparation•Self-paced

Software Engineering MasterTrack® Certificate

Expert feedback•Credit eligible

View all Computer Science Certificates

More Certificate Programs

Computer Science Physical Science and Engineering Social Sciences Language Learning

Launch or advance your career

Data Science

Data Scientist Data Analyst BI Analyst BI Developer Data Engineer

Business

Agile Project Manager (IT)Digital Marketing Specialist Digital Marketing Manager Project Coordinator Project Manager Social Media Coordinator

Computer Science

Computer User Support Specialist Network Administrator Network Engineer Product Designer

Arts and Humanities

Graphic Designer UI/UX Designer View all Professional Certificates

Data Science

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Python SQL Microsoft Excel Excel Machine Learning Data Science Power BI Artificial Intelligence Statistics Free Courses Data Science View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

University of Colorado Boulder

Master of Science in Data Science

University of Illinois at Urbana-Champaign

Master in Computer Science

Master of Data Science

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Google Data Analytics

No prerequisites•Self-paced

IBM Data Science

No prerequisites•Self-paced

Machine Learning for Analytics MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Business

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Project Management Microsoft Excel Excel Blockchain Digital Marketing Stock Market Power BI Marketing Accounting Free Courses Data Science View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

University of Illinois at Urbana-Champaign

Master of Business Administration (iMBA)

University of Illinois at Urbana-Champaign

Master of Science in Management

Macquarie University

Global Master of Business Administration (Global MBA)

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Facebook Social Media Marketing

No prerequisites•Self-paced

Google Project Management:

No prerequisites•Self-paced

IBM Machine Learning

View all Certificates

Computer Science

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Python Java Cybersecurity Blockchain Web Development C++AWS Artificial Intelligence Javascript Guided Projects View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

Penn Engineering

Master of Computer and Information Technology

Arizona State University

Master of Computer Science

Master of Computer Vision

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

AI and Machine Learning MasterTrack® Certificate

Expert feedback•Credit eligible

DeepLearning.AI TensorFlow Developer

Certification preparation•Self-paced

Software Engineering MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Information Technology

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Google Cybersecurity AWS Linux DevOps Ethical Hacking Microsoft Azure Google Cloud Kubernetes View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

Penn Engineering

Master of Computer and Information Technology

Arizona State University

Master of Computer Science

University of Illinois at Urbana-Champaign

Master of Computer Science

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Google IT Support

No prerequisites•Self-paced

Preparing for Google Cloud Certification: Cloud Architect

Certification preparation•Self-paced

Cybersecurity MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Language Learning

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

English Korean French Language English Speaking French Japanese Chinese English Grammar English Writing Korean Language View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

National Research Tomsk State University

Global MA in English Language Teaching Leadership

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Arizona State University TESOL

Certification preparation•Self-paced

English Proficiency for Graduate Studies Certificate

Expert feedback•Live sessions

View all Certificates

Health

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Psychology Medicine Biology Medical Neuroscience Bioinformatics Mental Health Anatomy Free Courses Psychology Agriculture View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

Imperial College London

Global Master of Public Health

University of Michigan

Master of Science in Population and Health Sciences

University of Michigan

Master of Public Health

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Health Informatics MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Personal Development

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Communication Skills Soft Skills Critical Thinking Public Speaking Emotional Intelligence Free Courses Psychology Teaching Mindfulness Positive Psychology Teaching English View all skills

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

CertNexus Certified Ethical Emerging Technologist

Certification preparation•Self-paced

ICPM Certified Supervisor

Certification preparation•Self-paced

View all Certificates

Physical Science and Engineering

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Matlab Physics Calculus Civil Engineering Electronics Autocad GIS Embedded Systems Chemistry Arduino View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

University of Colorado Boulder

Master of Science in Electrical Engineering

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

IBM AI Engineering

Preparing for Google Cloud Certification: Cloud Engineer

Certification preparation•Self-paced

Industrial Internet of Things MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Social Sciences

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Law Economics Sustainability Journalism International Relations Teaching Sociology Teaching English Education Macroeconomics View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

Imperial College London

Global Master of Public Health

University of Michigan

Master of Public Health

O.P. Jindal Global University

M.A. in International Relations, Security, and Strategy

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Social Work MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Arts and Humanities

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Art Photoshop Music Photography Creative Writing Drawing Film Art History Music Theory Philosophy View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

University of North Texas

Bachelor of Applied Arts and Sciences

View all degrees

Certificate programs

In 3-9 months, gain the skills to break into a new career or take your career to the next level.

Google UX Design

No prerequisites•Self-paced

UX Design MasterTrack® Certificate

Expert feedback•Credit eligible

View all Certificates

Math and Logic

Get started

Free courses Most popular Guided Projects under 2 hours

Popular skills

Calculus Mathematics Linear Algebra Algebra Math Probability Mathematics For Machine Learning Optimization Pre Calculus Multivariable Calculus View all skills

Degrees

Breakthrough pricing on 100% online degrees designed to fit into your life.

University of London

Bachelor of Science in Computer Science

View all degrees

Browse
Top Courses
Profile
My Purchases
Get 50% Off
Settings
Updates
Accomplishments
Help Center

Discrete Math and Analyzing Social Graphs
Week 4
Coloring

QuizQuiz • 15 min15 minutes

Coloring

Submit your assignment

Due DateMar 16, 3:59 AM EDTMarch 16, 3:59 AM EDT

Receive grade

To Pass100% or higher

Grade

100%

We keep your highest score

Confirm Navigation

Are you sure you want to leave this page?

Coloring

Graded Quiz • 15 min

Due Mar 16, 3:59 AM EDT

Congratulations! You passed!

To Pass 100% or higher

Grade

100%

Coloring

Latest Submission Grade

100%

1.

Question 1

What is the smallest number of colors needed for coloring this graph properly?

2 / 2 points

4

Correct

On one hand, this graph can be properly colored in 4 colors (actually, this is an instance of the 4-color theorem, but one can also do it manually). On the other hand, 3 colors are insufficient. Take a look at vertex 9. It is surrounded by an odd number of vertices in a cycle (10, 11, 6, 5, 1). In a proper coloring, these vertices will use at least 3 colors. The color of vertex 9 should be distinct from all of them. Thus, we need the 4th color.

2.

Question 2

Which of the following graphs are bipartite?

1 / 1 point

Correct

Indeed, this graph is bipartite: edges go only between the upper part and the lower one.

Correct

In fact, any tree is bipartite: the greedy algorithm for 2-coloring could never fail on a tree, since it tries each vertex only once.

Correct

This graph is bipartite, which is established by the following 2-coloring.